// Knight.cpp : main project file.

#include "stdafx.h"
#include "Form1.h"
#include <cstdlib> 

using namespace Knight;
using namespace System::Drawing;
using namespace System::Drawing::Drawing2D;


namespace Knight {
    [STAThreadAttribute]
    int main(array<System::String ^> ^args)
    {
	    // Enabling Windows XP visual effects before any controls are created
	    Application::EnableVisualStyles();
	    Application::SetCompatibleTextRenderingDefault(false); 

	    // Create the main window and run it
	    Application::Run(gcnew Form1());
	    return 0;
    }
    void Form1::button1_Click(System::Object ^sender, System::EventArgs ^e){
        int newCSIZE = Convert::ToInt16(numericUpDown1->Text);
        if(newCSIZE < 3){
            MessageBox::Show("Invalid n! Must be >= 3");
            return;
        }
        int newDSIZE = Convert::ToInt16(numericUpDown2->Text);
        if(newDSIZE < 3){
            MessageBox::Show("Invalid m! Must be >= 3");
            return;
        }

        int targetTrials = Convert::ToInt16(numericUpDown3->Text);
        int totalTrials=0, numHamiltonian=0, numNonHamiltonian=0, numDiverge=0;
        int numHamiltonianEpochs=0, numNonHamiltonianEpochs=0;
        stopped = false;
        button1->Enabled = false;
        do{
        
            Initialize();

            int n;
            int t=0, diag=1, dU, k;
            register int sum_row;
            register int sum_col;
            int *U_, *V_, *D_;

            while(diag>0) {
                diag = 0; n = 1;

                for(i = 0; i < NSIZE; i++) {
                  U_ = U[i];
                  V_ = V[i];
                  D_ = D[i];
                  for(j = n; j < NSIZE; j++) {

                    if(D_[j] == 1) {
                        sum_row = 0; sum_col = 0;
                        for(k=0; k<NSIZE; k++) {
                            if(D_[k])
                                sum_row += V_[k]; //(V[i][k]*D[i][k]);
                            if(D[k][j])
                                sum_col += V[k][j]; //(V[k][j]*D[k][j]);
                        }
                        dU = -(sum_row-2)-(sum_col-2);
                    }else {
                        dU = 0;
                    }

                    U_[j] += dU;

                    if(U_[j] > 3) V_[j] = 1;
                    if(U_[j] < 0 ) V_[j] = 0;
    	    
                    if(V_[j] == 1) V[j][i] = 1;
                    if(V_[j] == 0) V[j][i] = 0;

                    diag += (dU == 0 ? 0 : 1);
                  }
                  n++;
                }

                if(t>1000) break;
                t++;

            }

            if(stopped) break;

            if(t>1000){
                numDiverge++;
                hamiltonian = false;
                if(checkBox1->Checked) DrawNeurons();
            }else if(CheckHamiltonian()){
                numHamiltonian++;
                hamiltonian = true;
                numHamiltonianEpochs += t;
                DrawNeurons();
                Refresh();
            }else{
                hamiltonian = false;
                numNonHamiltonian++;
                numNonHamiltonianEpochs += t;
                if(checkBox1->Checked){
                    DrawNeurons();
                    Refresh();
                }
            }
            totalTrials++;

        }while(totalTrials < targetTrials);

        button1->Enabled = true;
        stopped = true;
    }
    void Form1::OnPaint(System::Windows::Forms::PaintEventArgs ^e){
        e->Graphics->Clear(Color::White);
        e->Graphics->SmoothingMode = SmoothingMode::None;
        e->Graphics->DrawImageUnscaled(drawing, 0, 0);
    }
    void Form1::OnPaintBackground(System::Windows::Forms::PaintEventArgs ^e)    {        
    }
    void Form1::Initialize(){
        int n, m, count;
        int tempCSize = Convert::ToInt16(this->numericUpDown1->Text);
        int tempDSize = Convert::ToInt16(this->numericUpDown2->Text);
        if((tempCSize != CSIZE) || (tempDSize != DSIZE)){
            //clear old arrays
            if(V){ for(int i=0; i<NSIZE; i++) delete [] V[i]; delete [] V; }
            if(U){ for(int i=0; i<NSIZE; i++) delete [] U[i]; delete [] U; }
            if(D){ for(int i=0; i<NSIZE; i++) delete [] D[i]; delete [] D; }
            if(A){ for(int i=0; i<NSIZE; i++) delete [] A[i]; delete [] A; }

            for(int i=0; i< Count; i++) delete (link*)links[i];
            Count = 0;

            CSIZE = tempCSize;
            DSIZE = tempDSize;
            NSIZE = CSIZE*DSIZE;

		    if(drawing)
                delete drawing;
            drawing = gcnew Bitmap(this->Width,this->Height);
            XSIZE = (this->Width)/(CSIZE+ 2);
            YSIZE = (this->Height - 80)/(DSIZE+2);
            //create new arrays
            V = new int*[NSIZE];
                for(int i=0; i<NSIZE; i++) V[i] = new int[NSIZE];
            U = new int*[NSIZE];
                for(int i=0; i<NSIZE; i++) U[i] = new int[NSIZE];
            D = new int*[NSIZE];
                for(int i=0; i<NSIZE; i++) D[i] = new int[NSIZE];
            A = new int*[NSIZE];
                for(int i=0; i<NSIZE; i++) A[i] = new int[2];

            int numLinks;
            if(CSIZE > DSIZE) numLinks = 4*(CSIZE-2)*(CSIZE-1)+1;
            else numLinks = 4*(DSIZE-2)*(DSIZE-1)+1;
            links = (link **)malloc(numLinks * sizeof(link *));
            for(int i=0; i<numLinks; i++)
                { link* l = new link; links[i] = l;Count++; }
        }
        for(m=0; m < NSIZE; m++) {
	        for(n=0; n < NSIZE; n++) {
	            U[m][n] = -(int)(rand()%CSIZE);
	            V[m][n] = 0;
	        }
        }

        for(m = 0; m < NSIZE; m++)
            for(n = 0; n < NSIZE; n++)
                D[m][n] = 0;

        for(i = 0; i < NSIZE; i++) {
          if(i+1 < CSIZE*(i/CSIZE+1) && i+1-(2*CSIZE) >= 0)
            D[i][i+1-(2*CSIZE)] = 1;
          if(i+2 < CSIZE*(i/CSIZE+1) && i+2-CSIZE >= 0)
            D[i][i+2-CSIZE] = 1;
          if(i+2 < CSIZE*(i/CSIZE+1) && i+2+CSIZE < NSIZE)
            D[i][i+2+CSIZE] = 1;
          if(i+1 < CSIZE*(i/CSIZE+1) && i+1+(2*CSIZE) < NSIZE)
            D[i][i+1+(2*CSIZE)] = 1;
          if(i-1 >= CSIZE*(i/CSIZE) && i-1+(2*CSIZE) < NSIZE)
            D[i][i-1+(2*CSIZE)] = 1;
          if(i-2 >= CSIZE*(i/CSIZE) && i-2+CSIZE < NSIZE)
            D[i][i-2+CSIZE] = 1;
          if(i-2 >= CSIZE*(i/CSIZE) && i-2-CSIZE >= 0)
            D[i][i-2-CSIZE] = 1;
          if(i-1 >= CSIZE*(i/CSIZE) && i-1-(2*CSIZE) >= 0)
            D[i][i-1-(2*CSIZE)] = 1;
        }

        count = -1;
        for(i=0; i<NSIZE; i++){
          if(i%CSIZE == 0){
            count++;
            A[i][0] = XSIZE+XSIZE/2;
            A[i][1] = YSIZE+YSIZE/2+YSIZE*count;
          }
          else {
            A[i][0] = XSIZE+XSIZE/2+XSIZE*(i%CSIZE);
            A[i][1] = YSIZE+YSIZE/2+YSIZE*count;
          }
        }
    }
    bool Form1::CheckHamiltonian(){
        int p=1;
        int linkNum=0, linkCount;
        for(int m=0; m<NSIZE; m++) {
            for(int n=p; n<NSIZE; n++) {
                if(V[m][n] == 1) {
                    link* l = (link*)links[linkNum++];
                    l->i = m; l->j = n; l->visited = false;
                }
            }
            p++;
        }
        linkCount = linkNum;
        //now traverse links
        linkNum=0;
        int numTraversed=0;
        link* l = (link*)links[linkNum];
        int startPt = l->i;
        int nextPt = l->j;
        bool found;
        while(1){
            l->visited = true;
            found = false;
            //find a link with the next endpoint
            for(i=0; i<linkCount; i++){
                link* l2 = (link*)links[i];
                if(l2->visited) continue;
                if(l2->i == nextPt){
                    l = l2; nextPt = l2->j; found = true;
                    numTraversed++; break;
                }
                if(l2->j == nextPt){
                    l = l2; nextPt = l2->i; found = true;
                    numTraversed++; break;
                }
            }
            if(!found) break;
            if((nextPt == startPt) || (numTraversed >= (linkCount-1))) break;
        }
        if((nextPt == startPt) && (numTraversed >= (linkCount-1))){
            return true;
        }
        return false;
    }
    void Form1::DrawNeurons(){    
        Graphics ^g = Graphics::FromImage(drawing);
        g->Clear(Color::White );
	    int n, m, p;

        g->FillRectangle(Brushes::White ,XSIZE, YSIZE, (CSIZE+1)*XSIZE, (DSIZE+1)*YSIZE);
        Pen ^pen = gcnew Pen(Color::Black, 2);
	    
	    for(n=0; n<=CSIZE ; n++) 
		    g->DrawLine(pen, XSIZE*(n+1), 80+YSIZE,XSIZE*(n+1), 80+YSIZE+DSIZE*YSIZE);

	    for(m=0; m<=DSIZE ; m++) 
            g->DrawLine(pen, XSIZE, 80+YSIZE*(m+1),XSIZE+CSIZE*XSIZE+1, 80+YSIZE*(m+1)); 

	    for(int n=0; n<CSIZE; n++)
		    for(int m=0; m<DSIZE; m++)
                g->FillEllipse(Brushes::Olive , XSIZE*(n+1) + XSIZE/2 - 3 , 80+YSIZE*(m+1) + YSIZE/2 - 3, 6, 6);

        p = 1;

        if(hamiltonian){
            pen->Width = 2;
            pen->Color = Color::Red;
        }
        else{
            pen->Width = 1;
            pen->Color = Color::Blue;
        }

	    for(m=0; m<NSIZE; m++){
		    for(n=p; n<NSIZE; n++){
			    if(V[m][n] == 1) 
				    g->DrawLine(pen,A[m][0], 80+A[m][1],A[n][0], 80+A[n][1]);
		    }
	        p++;
        }

    }
}